/*
 * @lc app=leetcode.cn id=126 lang=golang
 *
 * [126] 单词接龙 II
 */

// 2. 双向广度优先
// @lc code=start
func findLadders(beginWord string, endWord string, wordList []string) (ans [][]string) {
	if !contain(wordList, endWord) {
		return
	}

	allWord := "abcdefghijklmnopqrstuvwxyz"
	preHistory, postHistory := []string{beginWord}, []string{endWord}
	var recursion func(preMap, postMap map[string][][]string)
	recursion = func(preMap, postMap map[string][][]string) {
		for k1, v1 := range preMap {
			for k2, v2 := range postMap {
				if k1 == k2 {
					for i := 0; i < len(v1); i++ {
						for j := 0; j < len(v2); j++ {
							temp := make([]string, len(v1[i]))
							copy(temp, v1[i])
							for k := len(v2[j]) - 2; k >= 0; k-- {
								temp = append(temp, v2[j][k])
							}
							ans = append(ans, temp)
						}
					}

				}
			}
		}

		if len(ans) > 0 {
			return
		}

		for k1, v1 := range preMap { // a, b, [a, b, c]
			for k2, v2 := range postMap {
				if compare(k1, k2) {
					for i := 0; i < len(v1); i++ {
						for j := 0; j < len(v2); j++ {
							temp := make([]string, len(v1[i]))
							copy(temp, v1[i])
							for k := len(v2[j]) - 1; k >= 0; k-- {
								temp = append(temp, v2[j][k])
							}
							ans = append(ans, temp)
						}
					}

				}
			}
		}

		if len(ans) > 0 {
			return
		}

		preNextLevel := make(map[string][][]string)
		for k, v := range preMap {
			for i := 0; i < len(k); i++ {
				for j := 0; j < len(allWord); j++ {
					if k[i] == allWord[j] {
						continue
					}

					bytes := []byte(k)
					bytes[i] = allWord[j]
					temp := string(bytes)

					if contain(wordList, temp) && !contain(preHistory, temp) {
						dd := make([][]string, len(v))
						// copy(dd, v) 不能这么搞，不然下面append的时候会改变已经装填好的数据

						for ii, vv := range v {
							d := make([]string, len(vv))
							copy(d, vv)
							dd[ii] = d
						}

						for s := 0; s < len(dd); s++ {
							dd[s] = append(dd[s], temp)
						}

						preNextLevel[temp] = append(preNextLevel[temp], dd...)
					}
				}
			}
		}

		postNextLevel := make(map[string][][]string)
		for k, v := range postMap {
			for i := 0; i < len(k); i++ {
				for j := 0; j < len(allWord); j++ {
					if k[i] == allWord[j] {
						continue
					}

					bytes := []byte(k)
					bytes[i] = allWord[j]
					temp := string(bytes)

					if contain(wordList, temp) && !contain(postHistory, temp) {
						dd := make([][]string, len(v))
						for ii, vv := range v {
							d := make([]string, len(vv))
							copy(d, vv)
							dd[ii] = d
						}
						for s := 0; s < len(dd); s++ {
							dd[s] = append(dd[s], temp)
						}

						postNextLevel[temp] = append(postNextLevel[temp], dd...)
					}
				}
			}
		}

		if len(preNextLevel) > 0 || len(postNextLevel) > 0 {
			for k, _ := range preNextLevel { // 不能在上面加history，ad,ab,ac 都可以变成ar
				preHistory = append(preHistory, k)
			}
			for k, _ := range postNextLevel {
				postHistory = append(postHistory, k)
			}
			recursion(preNextLevel, postNextLevel)
		}
	}

	map1 := make(map[string][][]string)
	map1[beginWord] = [][]string{{beginWord}}

	map2 := make(map[string][][]string)
	map2[endWord] = [][]string{{endWord}}
	recursion(map1, map2)

	return ans
}

func contain(wordList []string, value string) bool {
	for i := 0; i < len(wordList); i++ {
		if wordList[i] == value {
			return true
		}
	}
	return false
}

func compare(str1, str2 string) bool {
	if len(str1) != len(str2) {
		return false
	}

	count := 0
	for i := 0; i < len(str1); i++ {
		if str1[i] != str2[i] {
			count++
		}
	}

	return count == 1
}

// @lc code=end

// 1. 广度优先 超时 24/36
// @lc code=start
func findLadders(beginWord string, endWord string, wordList []string) (ans [][]string) {
	if !contain(wordList, endWord) {
		return
	}

	allWord := "qwertyuiopasdfghjklzxcvbnm"
	var recursion func(wordMap map[string][][]string, history []string)
	recursion = func(wordMap map[string][][]string, history []string) {
		for k, v := range wordMap {
			if k == endWord {
				for i := 0; i < len(v); i++ {
					ans = append(ans, v[i])
				}
				return
			}
		}

		nextLevel := make(map[string][][]string)
		for k, v := range wordMap {
			for i := 0; i < len(k); i++ {
				for j := 0; j < len(allWord); j++ {
					if k[i] == allWord[j] {
						continue
					}

					bytes := []byte(k)
					bytes[i] = allWord[j]
					temp := string(bytes)

					if contain(wordList, temp) && !contain(history, temp) {
						dd := make([][]string, len(v))
						copy(dd, v)
						for s := 0; s < len(dd); s++ {
							dd[s] = append(dd[s], temp)
						}

						nextLevel[temp] = append(nextLevel[temp], dd...)
					}
				}
			}
		}

		if len(nextLevel) > 0 {
			for k, _ := range nextLevel {
				history = append(history, k)
			}
			recursion(nextLevel, history)
		}
	}
	map1 := make(map[string][][]string)
	map1[beginWord] = [][]string{{beginWord}}
	recursion(map1, []string{beginWord})

	return ans
}

func contain(wordList []string, value string) bool {
	for i := 0; i < len(wordList); i++ {
		if wordList[i] == value {
			return true
		}
	}
	return false
}

// @lc code=end

 